#include <bits/stdc++.h>
using namespace std;

/*
3408. 设计任务管理器
已解答
中等
相关标签
premium lock icon
相关企业
一个任务管理器系统可以让用户管理他们的任务，每个任务有一个优先级。这个系统需要高效地处理添加、修改、执行和删除任务的操作。

请你设计一个 TaskManager 类：

TaskManager(vector<vector<int>>& tasks) 初始化任务管理器，初始化的数组格式为 [userId, taskId, priority] ，表示给 userId 添加一个优先级为 priority 的任务 taskId 。

void add(int userId, int taskId, int priority) 表示给用户 userId 添加一个优先级为 priority 的任务 taskId ，输入 保证 taskId 不在系统中。

void edit(int taskId, int newPriority) 更新已经存在的任务 taskId 的优先级为 newPriority 。输入 保证 taskId 存在于系统中。

void rmv(int taskId) 从系统中删除任务 taskId 。输入 保证 taskId 存在于系统中。

int execTop() 执行所有用户的任务中优先级 最高 的任务，如果有多个任务优先级相同且都为 最高 ，执行 taskId 最大的一个任务。执行完任务后，taskId 从系统中 删除 。同时请你返回这个任务所属的用户 userId 。如果不存在任何任务，返回 -1 。

注意 ，一个用户可能被安排多个任务。

 

示例 1：

输入：
["TaskManager", "add", "edit", "execTop", "rmv", "add", "execTop"]
[[[[1, 101, 10], [2, 102, 20], [3, 103, 15]]], [4, 104, 5], [102, 8], [], [101], [5, 105, 15], []]

输出：
[null, null, null, 3, null, null, 5]

解释：

TaskManager taskManager = new TaskManager([[1, 101, 10], [2, 102, 20], [3, 103, 15]]); // 分别给用户 1 ，2 和 3 初始化一个任务。
taskManager.add(4, 104, 5); // 给用户 4 添加优先级为 5 的任务 104 。
taskManager.edit(102, 8); // 更新任务 102 的优先级为 8 。
taskManager.execTop(); // 返回 3 。执行用户 3 的任务 103 。
taskManager.rmv(101); // 将系统中的任务 101 删除。
taskManager.add(5, 105, 15); // 给用户 5 添加优先级为 15 的任务 105 。
taskManager.execTop(); // 返回 5 。执行用户 5 的任务 105 。
 

提示：

1 <= tasks.length <= 105
0 <= userId <= 105
0 <= taskId <= 105
0 <= priority <= 109
0 <= newPriority <= 109
add ，edit ，rmv 和 execTop 的总操作次数 加起来 不超过 2 * 105 次。
输入保证 taskId 是合法的。
*/

// 法一
class TaskManager {
// helper的 func 和 变量
private:
    // tool comnpare to 优先队列  font-->higher  if same  taskId>的infont
    struct Compare {
        bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
            if (a.first != b.first)     return a.first < b.first;
            else                        return a.second < b.second;
        }
    };

    // 任务info taskId -> {userId, priority}  快速查询任务所属用户和当前优先级
    unordered_map<int, pair<int, int>> taskInfo;
    // max_heap 存储(priority, taskId)，用于快速获取最高优先级任务
    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;

public:
    TaskManager(vector<vector<int>>& tasks) {
        // 迭代 init 任务list
        for (auto& task : tasks) {
            int userId = task[0];
            int taskId = task[1];
            int priority = task[2];

            // 基本任务信息
            taskInfo[taskId] = {userId, priority};
            pq.push({priority, taskId});    // 进优先队列
        }
    }
    
    // taskId 唯一
    void add(int userId, int taskId, int priority) {
        taskInfo[taskId] = {userId, priority};
        pq.push({priority, taskId});    // 进优先队列
    }
    
    // taskId must exist
    void edit(int taskId, int newPriority) {
        // change the 优先级
        taskInfo[taskId].second = newPriority;      // update
        pq.push({newPriority, taskId});  // 推送新状态到队列（旧状态会延迟删除）
    }
    
    void rmv(int taskId) {
        taskInfo.erase(taskId);  // 从信息表中删除，标记任务无效
    }
    
    int execTop() {
        // 按照优先级来执行  return userId
        // 清理队列中无效的任务
        while (!pq.empty()) {
            auto [priority, taskId] = pq.top();
            pq.pop();       // 队头的都pop

            // check 存在且优先级匹配
            if (taskInfo.count(taskId) && taskInfo[taskId].second == priority) {
                int userId = taskInfo[taskId].first;
                taskInfo.erase(taskId);
                return userId;
            }
        }
        // 无有效的就-1
        return -1;
    }
};

/**
 * Your TaskManager object will be instantiated and called as such:
 * TaskManager* obj = new TaskManager(tasks);
 * obj->add(userId,taskId,priority);
 * obj->edit(taskId,newPriority);
 * obj->rmv(taskId);
 * int param_4 = obj->execTop();
 */

// 法二
constexpr int N = 3e5 + 5;  // 最大任务数量上限，适配题目规模

// 自定义优先队列实现（性能优化：使用固定数组存储，避免动态内存分配）
namespace ea {
    template<typename _Tp, typename _Comp = std::less<_Tp>>
    struct priority_queue {
      inline void push(_Tp v) {_c[_n++] = v; std::push_heap(_c, _c+_n, _Comp{});}  // 插入并堆化
      inline void pop() {std::pop_heap(_c, _c+_n, _Comp{}); _n--;}  // 弹出堆顶并堆化
      inline const _Tp& top() const {return _c[0];}  // 获取堆顶元素（最高优先级）
      inline size_t size() const { return _n;}
      inline bool empty() const {return _n == 0;}

      _Tp _c[N];  // 固定数组存储元素，提升访问速度
      size_t _n {};  // 当前元素数量
    };
}

// 全局任务信息数组：[taskId] -> {userId, priority}（直接索引访问，O(1)效率）
array<int, 2> task[N];

class TaskManager {
    bitset<N/3> S{};  // 任务有效性标记：S[taskId] = 1表示有效，0表示已删除（bitset比哈希表更省空间且访问更快）
    // 优先队列：存储{priority, taskId, userId}，默认大顶堆（优先级高的在前；同优先级下taskId大的在前）
    ea::priority_queue<array<int, 3>> q;

public:
    // 初始化：批量添加初始任务
    TaskManager(vector<vector<int>>& tasks) {
        for (auto& t : tasks) add(t[0], t[1], t[2]);
    }
    
    // 添加任务：记录信息+标记有效+入队
    void add(int userId, int taskId, int priority) {
        task[taskId] = {userId, priority};  // 存储任务的用户ID和优先级
        S[taskId] = 1;  // 标记任务有效
        q.push({priority, taskId, userId});  // 加入优先队列，参与优先级排序
    }
    
    // 修改优先级：通过添加新状态到队列实现（旧状态会在执行时过滤，延迟删除策略）
    void edit(int taskId, int newPriority) {
        auto [uid, pri] = task[taskId];  // 获取当前用户ID
        add(uid, taskId, newPriority);   // 用新优先级重新入队（旧优先级条目会失效）
    }
    
    // 删除任务：仅标记无效（实际清理在执行时进行）
    void rmv(int taskId) {
        S[taskId] = 0;  // 标记任务无效，后续执行时会被过滤
    }
    
    // 执行最高优先级任务：返回所属用户ID
    int execTop() {
        while (!q.empty()) {
            auto [pri, tid, uid] = q.top(); q.pop();  // 取出堆顶任务
            
            // 检查任务有效性：1. 未被删除；2. 优先级与当前记录一致（排除edit后的旧条目）
            if (S[tid] && task[tid] == array<int, 2>{uid, pri}) {
                rmv(tid);  // 执行后标记为无效
                return uid;
            }
        }
        return -1;  // 无有效任务
    }
};

/**
 * Your TaskManager object will be instantiated and called as such:
 * TaskManager* obj = new TaskManager(tasks);
 * obj->add(userId,taskId,priority);
 * obj->edit(taskId,newPriority);
 * obj->rmv(taskId);
 * int param_4 = obj->execTop();
 */